
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        //判断特殊情况节省运行时间
        if (nums2.empty())
            return;
        //用 i , j , cur 三个指针 
        // i 指向 nums1 中最后一个非零元素
        int i = m - 1; 
         // j 指向 nums2 中最后一个元素
        int j = n - 1;
        // cur 指向 nums1 当前要填充的位置
        int cur = m + n - 1; 
        //同时遍历 nums1 和 nums2
        while (i >= 0 && j >= 0) { 
            //将较大的元素放到当前要填充的位置
            if (nums1[i] > nums2[j]) {
                nums1[cur] = nums1[i]; 
                //只需要更新 i 指针，不需要更新 j
                i--;
            } else {
                //将较大的元素放到当前要填充的位置
                nums1[cur] = nums2[j]; 
                //同理，只需要更新 j 指针
                j--;
            }
            //不管哪个大都要更新 cur 指针
            cur--;
        }
        //j大于等于0，说明 nums2 中还有剩余元素，然后将剩余的 nums2 中的元素放入 nums1 中
        while (j >= 0) {
            nums1[cur] = nums2[j];
            cur--;
            j--;
        }
    }
};